package Solutions

import "unsafe"

func shoppingOffers(price []int, special [][]int, needs []int) int {
	var cache = map[string]int{}
	var minPrice func(need []int) int
	minPrice = func(need []int) int {
		ss := covert(need)
		if v, ok := cache[ss]; ok {
			return v
		}
		pric := (1 << 63) - 1
		t := make([]int, len(need))
	outer:
		for i := range special {
			for j := 0; j < len(need); j++ {
				t[j] = need[j] - special[i][j]
				if t[j] < 0 {
					continue outer
				}
			}
			p := special[i][len(special[i])-1] + minPrice(t)
			if p < pric {
				pric = p
			}

		}
		pricT := 0
		for i := range need {
			pricT += need[i] * price[i]
		}
		if pricT < pric {
			pric = pricT
		}

		cache[ss] = pric
		return pric
	}
	return minPrice(needs)
}

func covert(arr []int) string {
	t := make([]int, len(arr))
	copy(t, arr)
	bs := *(*string)(unsafe.Pointer(&struct {
		Data unsafe.Pointer
		Len  int
	}{
		unsafe.Pointer(&t[0]),
		len(arr) * 8,
	}))

	return bs
}
